// 给定一个非空二叉树，返回其最大路径和。

// 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

// 示例 1:

// 输入: [1,2,3]

//        1
//       / \
//      2   3

// 输出: 6
// 示例 2:

// 输入: [-10,9,20,null,null,15,7]

//    -10
//    / \
//   9  20
//     /  \
//    15   7

// 输出: 42

#include <algorithm>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        func(root, res);
        return res;
    }
    int func(TreeNode* node, int& res) {
        if (!node) return 0;
        int left = max(func(node->left, res), 0);
        int right = max(func(node->right, res), 0);
        res = max(res, left + right + node->val); // 最大值一定是：当前节点+左子树+右子树
        return max(left, right) + node->val; // 当前节点的贡献值一定只能包含左右子树中的一个
    }
};

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return m_maxPathSum;
    }
private:
    int maxGain(TreeNode* node) {
        if (node == nullptr) return 0;
        // 递归计算左右子节点的最大贡献值，贡献值大于0时，才选取对应子节点
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        // 该节点的最大路径和等于节点值加左右子节点贡献值
        int temp = node->val + leftGain + rightGain;
        m_maxPathSum = max(m_maxPathSum, temp);

        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);
    }
    int m_maxPathSum{INT_MIN};
};